﻿#include <stdio.h>
#include <stdbool.h>

// 判断数组相等
bool isEquals(int* s1, int* s2, int size) {
	if (s1 == NULL || s2 == NULL) return false;
	for (int i = 0; i < size; i++) {
		if (s1[i] != s2[i]) {
			return false;
		}
	}
	return true;
}

bool checkInclusion(char* s1, char* s2) {
	if (s1 == NULL || s2 == NULL) return false;
	const int s1Len = strlen(s1);
	const int s2Len = strlen(s2);
	if (s1Len > s2Len) return false;
	// 处理s1字符串，因为题目要求不需要顺序，仅统计字符个数；且全小写字符，顾size=26的数组即可
	int *aryS1 = malloc(sizeof(int) * 26);
	memset(aryS1, 0, sizeof(int));
	// 处理s2字符串前s1.length长度，因为题设s2.length>=s1.length
	int *aryS2 = malloc(sizeof(int) * 26);
	memset(aryS2, 0, sizeof(int));
	// 循环遍历s1.length，统计s1字符，顺便统计s2前s1.length字符串
	const int charACode = 'a';
	for (int i = 0; i < s1Len; i++) {
		const int code1 = s1[i] - charACode;
		aryS1[code1]++;
		const int code2 = s2[i] - charACode;
		aryS2[code2]++;
	}
	// 比较一下字符串是否相等(直接使用vector提供的元素的比较重载符==),题意仅需找到一处匹配即可
	if (isEquals(aryS1, aryS2, 26)) {
		free(aryS1);
		aryS1 = NULL;
		free(aryS2);
		aryS2 = NULL;
		return true;
	}
	// 后续遍历，用双指针对数组aryS2直接进行维护，节省统计开销
	int right = s1Len;
	while (right < s2Len) {
		// fixed the aryS2
		aryS2[s2[right] - charACode]++;
		aryS2[s2[right - s1Len] - charACode]--;
		// 比较一下字符串是否相等，题意仅需找到一处匹配即可
		if (isEquals(aryS1, aryS2, 26)) {
			free(aryS1);
			aryS1 = NULL;
			free(aryS2);
			aryS2 = NULL;
			return true;
		}
		right++;
	}
	// free memory
	free(aryS1);
	aryS1 = NULL;
	free(aryS2);
	aryS2 = NULL;
	return false;
}

int main()
{
	char* s11 = "ab";
	char* s12 = "eidbaooo";
	printf("\nwant:true, ans = %d", checkInclusion(s11, s12));

	char* s21 = "ab";
	char* s22 = "eidboaoo";
	printf("\nwant:false, ans = %d", checkInclusion(s21, s22));

	return 0;
}